package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.difficulty.DYellow;
import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;
import pro.softzhang.algo.flag.theme.TPath;

/**
 *
 */
@KDynamicPlanning
@DYellow
@TPath
public class LC64_MinimumPathSum {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public int minPathSum(int[][] grid) {
            int[][] dp = new int[grid.length][grid[0].length];
            dp[0][0] = grid[0][0];

            for (int j = 1; j < grid[0].length; j++) {
                dp[0][j] = grid[0][j] + dp[0][j - 1];
            }

            for (int i = 1; i < grid.length; i++) {
                dp[i][0] = grid[i][0] + dp[i - 1][0];
                for (int j = 1; j < grid[0].length; j++) {
                    int prev = Math.min(dp[i - 1][j], dp[i][j - 1]);
                    dp[i][j] = grid[i][j] + prev;
                }
            }

            return dp[grid.length - 1][grid[0].length - 1];
        }
    }
}
